The present invention relates generally to variable length decoders used in data transmission systems, and more particularly, to a variable length decoder for decoding digital video data for high definition television (HDTV).
In digital video dam transmission systems, video data is encoded prior to being transmitted to a receiver, which decodes the encoded digital video data. The decoded digital video data is then output to a subsequent signal processing stage. To increase the data throughput and memory efficiency of such systems, statistical compression algorithms are used to compress and encode the digital video data. One such compression algorithm is the Huffman coding algorithm. Compressing the data typically results in data streams segmented into variable length code words rather than fixed length code words. Variable length decoders decode the variable length code words comprising the compressed data stream.
There are several presently available methods for decoding a sequence of variable length code words. The most prevalent methods are the tree searching algorithm and the table look-up technique.
The tree searching algorithm uses a bit-by-bit search through a code tree to find the end and value of each code word in the input bit stream. The coding tree includes leaves of known code words. The decoding process begins at the root of the coding tree and continues bit-by-bit to different branches of the coding tree, depending upon the decoded value of each successive bit in the bit stream. Eventually a leaf is reached and the end of the code word is detected. The code word is then segmented from the rest of the bit stream and the value of the detected code word is looked up and output from the variable length decoder. Decoding a bit stream using the tree searching algorithm is too slow for many high speed applications, since the decoding operation is performed at the bit rate rather than at the symbol rate. In this connection, decoding a bit stream at the bit rate does not satisfy the peak symbol rate requirements of an HDTV decoder.
To increase the data throughput of a variable length decoder, a table look-up decoder was developed, such as the one disclosed in U.S. Pat. No. 5,173,695, issued to Sun et al., the disclosure of which is herein incorporated by reference. The input of the table look-up decoder disclosed in the above-referenced patent is connected to the output of a rate buffer which receives a variable-word-length encoded bit stream at its input and outputs in parallel sequences of bits equal in length to the maximum length code word in the bit stream. These sequences are read into cascaded latches. The cascaded sequences in both latches are input to a barrel shifter which provides from its multi-bit input, a sliding decoding window to a table-lookup decoder. A control signal directly shifts the position of the decoding window of the barrel shifter as each code word is detected. To detect each code word, the initial bits in the decoding window are compared with code word entries in the table-lookup decoder. When a code word is detected, the corresponding code word length is added to the value of an accumulator with previously accumulated code word lengths to produce the control signal which directly shifts the decoding window by the number of bits in the just decoded word. When all of the bits in the first latch have been decoded, the next bit sequence in the buffer is input to the second latch while the previous bit sequence in the second latch is transferred to the first latch. The decoding window is then shifted to the beginning of the next undecoded sequence. The shifting of the decoding window and the decoding of the code word can be done in one clock cycle. As a result, the table look-up decoder is capable of decoding one code word per clock cycle regardless of its bit length, thereby dramatically increasing the data throughput of the decoder relative to the previously available tree searching algorithm decoder.
Although the table look-up decoder described in the above-referenced Sun et al. patent can decode at a symbol rate, rather than a bit rate, its actual speed of operation is limited by the propagation delay through the feedback loop consisting of the barrel shifter, word length decoder, and adder-accumulator. In HDTV applications, where the peak symbol rate can be over 100 million code words per second, decoding the whole picture at the symbol rate with a single table look-up decoder becomes impractical. In HDTV systems, the variable length decoder (VLD) is used to extract an entire picture from a rate buffer within the picture display time. If the VLD is not capable of operating at the peak symbol rate, then the pictures that carry more data than can be processed in a limited picture display time will cause the decoder to crash because the VLD will fail to extract all of the picture from the rate buffer. This may have devastating consequences for the picture quality. Thus, the VLD must decode words in the data stream at the peak symbol rate (PSR) in order to decode the pictures without a potential for such failure.
For HDTV systems which use the MPEG ("Moving Pictures Expert Group") protocol, a VLD throughput of 100 million or more code words per second is required. In addition to the technical problems associated with implementing the VLD itself with such high throughput, the high-speed VLD interface with the large capacity rate buffer is quite expensive with the currently available memory technology. The problem becomes more severe if price is an issue, since faster and more expensive memory devices such as static random access memories (SRAMs) and synchronous dynamic random access memories (SDRAMs) must be used, rather than slower and cheaper memory devices such as asynchronous DRAMs. Of course, the price of the memory is a particularly important consideration for a consumer product, such as an HDTV set.
In current implementations, HDTV systems are normally partitioned into multiple processing paths, using multiple VLDs to decode different portions of the picture in parallel. In such implementations, the VLD is one of the major bottlenecks. Because each partition of the picture may contain almost all of the picture information, multiple dedicated ping-pong buffers are required between all of the VLDs and the rate buffer, thereby dramatically increasing the amount of bit stream memory required for the system. For example, a partitioned decoding system having eight parallel VLDs requires eight ping-pong buffers, each one of the ping-pong buffers being twice the size of the rate buffer, thereby increasing the amount of required buffer memory by a factor of sixteen over a system having a single VLD.
In HDTV systems, the digital video data is a Huffman encoded bit stream which contains the code words to be decoded. In Huffman encoded bit streams, the code words which have the highest probability of occurence have the smallest number of bits, and code words which have the lowest probability of occurence have the greatest number of bits. Thus, Huffman encoded bit streams contain code words whose bit length is a function of the probability of occurence of the code word in the bit stream. The picture size is normally limited to a certain number of bits rather than a certain number of code words. If one code word is decoded per clock cycle, then the worst case scenario with respect to VLD throughput is the case where the entire picture is comprised of the smallest code words, since the average number of bits decoded per clock cycle would be at a minimum for this picture. Thus, the smallest code words in the Huffman encoded bit stream are the cause of such high peak symbol rates in HDTV systems.
Based on the above and foregoing, it can be appreciated that there presently exists a need in the art for a variable length decoder which overcomes the above-discussed drawbacks and shortcomings of the presently available technology, and which can be used to implement a single VLD HDTV decoder, rather than a partitioned HDTV decoder. More particularly, there presently exists a need in the art for a variable length decoder having a data throughput which is adequate for processing digital video data, but at a lower clock rate, thereby enabling the use of cheaper (slower) memory and making more practical the implementation of the variable length decoder.
As will become apparent hereinafter, the present invention fulfills this need in the art by providing a variable length decoder whose throughput per clock cycle is adaptively increased for a selected group of code words in the Huffman encoded bit stream which have a bit length less than a prescribed number, by decoding combinations of two or more code words from the selected group, during a single clock cycle, using a combination value look-up table which contains all possible combinations of code words from the selected group as additional entries. Since these smaller code words are statistically the most frequently occuring code words in the Huffman encoded bit stream, the throughput of the VLD of the present invention is significantly higher than that of the presently available VLDs, at a clock rate that is significantly lower than that of the presently available VLDs. In addition to this improved statistical performance due to adaptive acceleration in decoding code words within the selected group, the VLD of the present invention also guarantees a higher average minimum code word length, thereby enabling a reduction in the clock rate without sacrificing throughput.